Search results for "Rural Postman Problem"

showing 10 items of 16 documents

The Hierarchical Mixed Rural Postman Problem: Polyhedral analysis and a branch-and-cut algorithm

2017

[EN] The Hierarchical Mixed Rural Postman Problem is defined on a mixed graph where arcs and edges that require a service are divided into clusters' that have to be serviced in a hierarchical order. The problem generalizes the Mixed Rural Postman Problem and thus is NP-hard. In this paper, we provide a polyhedral analysis of the problem and propose a branch-and-cut algorithm for its solution based on the introduced classes of valid inequalities. Extensive computational experiments are reported on benchmark instances. The exact approach allows to find the optimal solutions in less than 1 hour for instances with up to 999 vertices, 2678 links, and five clusters.

Information Systems and ManagementHierarchical Routing ProblemsGeneral Computer Science0211 other engineering and technologiesMixed graph02 engineering and technologyManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringCombinatorics0502 economics and businessOrder (group theory)Mixed Rural Postman ProblemPolyhedral analysisBranch-and-cut Hierarchical Routing Problems Mixed Rural Postman Problem Polyhedral analysis Modeling and Simulation Management Science and Operations Research Information Systems and ManagementMathematicsDiscrete mathematics050210 logistics & transportation021103 operations research05 social sciencesBranch-and-cutModeling and SimulationBenchmark (computing)Polyhedral analysisMATEMATICA APLICADABranch and cutAlgorithmEuropean Journal of Operational Research
researchProduct

The stacker crane problem and the directed general routing problem

2015

[EN] This article deals with the polyhedral description and the resolution of the directed general routing problem (DGRP) and the stacker crane problem (SCP). The DGRP contains a large number of important arc and node routing problems as special cases, including the SCP. Large families of facet-defining inequalities for the DGRP are described and a branch-and-cut algorithm for these problems is presented. Extensive computational experiments over different sets of DGRP and SCP instances are included.

Mathematical optimizationDirected general routing problemStacker crane problemComputer Networks and CommunicationsStackerNode (networking)Branch-and-cut algorithmDirected graphResolution (logic)Directed rural postman problemHardware and ArchitectureRouting (electronic design automation)MATEMATICA APLICADASoftwareInformation SystemsMathematics
researchProduct

New Heuristic Algorithms for the Windy Rural Postman Problem

2005

[EN] In this paper we deal with the windy rural postman problem. This problem generalizes several important arc routing problems and has interesting real-life applications. Here, we present several heuristics whose study has lead to the design of a scatter search algorithm for the windy rural postman problem. Extensive computational experiments over different sets of instances, with sizes up to 988 nodes and 3952 edges, are also presented. (c) 2004 Elsevier Ltd. All rights reserved.

Arc routingMathematical optimizationGeneral Computer ScienceHeuristic (computer science)MetaheuristicsManagement Science and Operations ResearchRural postman problemSearch algorithmModeling and SimulationHeuristicsHeuristicsWindy rural postman problemMATEMATICA APLICADAArc routingAlgorithmMathematics
researchProduct

New facets and an enhanced branch-and-cut for the min-max K -vehicles windy rural postman problem

2011

[EN] The min-max windy rural postman problem is a multiple vehicle version of the windy rural postman problem, WRPP, which consists of minimizing the length of the longest route to find a set of balanced routes for the vehicles. In a previous paper, an ILP formulation and a partial polyhedral study were presented, and a preliminary branch-and-cut algorithm that produced some promising computational results was implemented. In this article, we present further results for this problem. We describe several new facet-inducing inequalities obtained from the WRPP, as well as some inequalities that have to be satisfied by any optimal solution. We present an enhanced branch-and-cut algorithm that t…

Postman problemsMathematical optimizationComputer Networks and CommunicationsFacetsWindy postman problemSet (abstract data type)Rural postman problemWindy rural postman problemsHardware and ArchitectureLarge set (Ramsey theory)Multi-vehiclesWindy rural postman problemMATEMATICA APLICADABranch and cutMetaheuristicAlgorithmsSoftwareMultivehicleInformation SystemsMathematicsNetworks
researchProduct

New Results on the Mixed General Routing Problem

2005

[EN] In this paper, we deal with the polyhedral description and the resolution of the Mixed General Routing Problem. This problem, in which the service activity occurs both at some of the nodes and at some of the arcs and edges of a mixed graph, contains a large number of important arc and node routing problems as special cases. Here, a large family of facet-defining inequalities, the Honeycomb inequalities, is described. Furthermore, a cutting-plane algorithm for this problem that incorporates new separation procedures for the K-C, Regular Path-Bridge, and Honeycomb inequalities is presented. Branch and bound is invoked when the final solution of the cutting-plane procedure is fractional. …

Mathematical optimizationmedicine.medical_specialtyBranch and boundPolyhedral combinatoricsMixed graphHoneycomb (geometry)Mixed rural postman problemManagement Science and Operations ResearchPolyhedral combinatoricsComputer Science ApplicationsRural postman problemVehicle routing problemmedicineDestination-Sequenced Distance Vector routingRouting (electronic design automation)General routing problemMATEMATICA APLICADACutting-plane methodMathematics
researchProduct

A comparison of two different formulations for Arc Routing Problems on Mixed graphs

2006

[EN] Arc routing problems on mixed graphs have been modelled in the literature either using just one variable per edge or associating to each edge two variables, each one representing its traversal in the corresponding direction. In this paper, and using the mixed general routing problem as an example, we compare theoretical and computationally both formulations as well as the lower bounds obtained from them using Linear Programming based methods. Extensive computational experiments, including some big and newly generated random instances, are presented.

Arc routingGeneral Computer ScienceLinear programmingMixed Chinese postman problemMixed graphMixed rural postman problemManagement Science and Operations ResearchRoute inspection problemTree traversalModeling and SimulationEnhanced Data Rates for GSM EvolutionRouting (electronic design automation)Mixed general routing problemMATEMATICA APLICADAAlgorithmArc routingMathematicsVariable (mathematics)
researchProduct

A New Branch-and-Cut Algorithm for the Generalized Directed Rural Postman Problem

2016

The generalized directed rural postman problem, also known as the close-enough arc routing problem, is an arc routing problem with some interesting real-life applications, such as routing for meter reading. In this article we introduce two new formulations for this problem as well as various families of new valid inequalities that are used to design and implement a branch-and-cut algorithm. The computational results obtained on test bed instances from the literature show that this algorithm outperforms the existing exact methods

050210 logistics & transportationMathematical optimization021103 operations research05 social sciences0211 other engineering and technologiesTransportation02 engineering and technologyTravelling salesman problemClose-enough arc routing problemBranch-and-cut0502 economics and businessGeneralized rural postman problemRouting (electronic design automation)MATEMATICA APLICADABranch and cutArc routingAlgorithmAutomatic meter readingCivil and Structural EngineeringMathematics
researchProduct

A Branch-Price-and-Cut Algorithm for the Min-Max k -Vehicle Windy Rural Postman Problem

2013

[EN] The min-max k -vehicles windy rural postman problem consists of minimizing the maximal distance traveled by a vehicle to find a set of balanced routes that jointly service all the required edges in a windy graph. This is a very difficult problem, for which a branch-and-cut algorithm has already been proposed, providing good results when the number of vehicles is small. In this article, we present a branch-price-and-cut method capable of obtaining optimal solutions for this problem when the number of vehicles is larger for the same set of required edges. Extensive computational results on instances from the literature are presented.

Difficult problemService (systems architecture)Mathematical optimizationComputer Networks and CommunicationsBranch and priceColumn generationSet (abstract data type)Rural postman problemHardware and ArchitectureCutting planesGraph (abstract data type)Branch-and-priceColumn generationWindy rural postman problemMATEMATICA APLICADAAlgorithmSoftwareInformation SystemsMathematicsMultivehicle
researchProduct

Lower bounds and heuristics for the Windy Rural Postman Problem

2020

[EN] In this paper we present several heuristic algorithms and a cutting-plane algorithm for the Windy Rural Postman Problem. This problem contains several important Arc Routing Problems as special cases and has very interesting real-life applications. Extensive computational experiments over different sets of instances are also presented.

Mathematical optimizationInformation Systems and ManagementGeneral Computer ScienceHeuristic (computer science)Management Science and Operations ResearchUpper and lower boundsIndustrial and Manufacturing EngineeringWindy Rural Postman ProblemModeling and SimulationCutting planesHeuristicsRouting (electronic design automation)HeuristicsMATEMATICA APLICADAAlgorithmArc routingCutting-plane methodMathematicsRouting
researchProduct

Drone arc routing problems

2018

[EN] In this article, we present some drone arc routing problems (Drone ARPs) and study their relation with well-known postman ARPs. Applications for Drone ARPs include traffic monitoring by flying over roadways, infrastructure inspection such as by flying along power transmission lines, pipelines or fences, and surveillance along linear features such as coastlines or territorial borders. Unlike the postmen in traditional ARPs, drones can travel directly between any two points in the plane without following the edges of the network. As a consequence, a drone route may service only part of an edge, with multiple routes being used to cover the entire edge. Thus the Drone ARPs are continuous o…

050210 logistics & transportation021103 operations researchComputer Networks and Communicationsbusiness.industry05 social sciences0211 other engineering and technologiesEuropean Regional Development Fund02 engineering and technologyDroneRural postman problemHardware and ArchitecturePolitical science0502 economics and businessCutting path problemsTelecommunicationsbusinessMATEMATICA APLICADAArc routingSoftwareInformation SystemsDrones
researchProduct